public class Solution {

    /**
     * 37. 解数独
     * 编写一个程序，通过填充空格来解决数独问题。
     * <p>
     * 数独的解法需 遵循如下规则：
     * <p>
     * 数字1-9在每一行只能出现一次。
     * 数字1-9在每一列只能出现一次。
     * 数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）
     * 数独部分空格内已填入了数字，空白格用'.'表示。
     */
    private static final int V1 = 1;
    private static final int V2 = 2;
    private static final int V3 = 4;
    private static final int V4 = 8;
    private static final int V5 = 16;
    private static final int V6 = 32;
    private static final int V7 = 64;
    private static final int V8 = 128;
    private static final int V9 = 256;
    private static final int CANDIDATE = 0b1000000000;
    private static final int CANDIDATE_CANCEL = 0b0111111111;
    private static final int ALL = 0b111111111;

    /*
     * 值存储结构改变. 按位表达值.
     * 高10位为1表示该位置未确定值.
     */
    public static void solveSudoku(char[][] board) {
        //转换类型 使用二进制表达
        int[][] sudo = new int[9][9];
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                sudo[r][c] = tran(board[r][c]);
            }
        }

        int leftNum = ruleSolution(sudo);
        if (leftNum > 0) {
            assumeSolution(sudo);
        }

        //回写结果
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                int v = sudo[r][c];
                v = tran(v);
                board[r][c] = (char) (v + 48);
            }
        }
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                System.out.print(board[r][c] + " | ");
            }
            System.out.println();
        }
    }

    public static boolean assumeSolution(int[][] sudo) {
        int original = 0, or = 0, oc = 0, tmp = 0;
        FIND:
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                int v = sudo[r][c];
                if (v == CANDIDATE) {
                    return false;
                }
                if ((v & CANDIDATE) == CANDIDATE) {
                    or = r;
                    oc = c;
                    original = v;
                    tmp = v;
                    break FIND;
                }
            }
        }

        System.out.println("r:" + or + " c:" + oc + " v:" + Integer.toBinaryString(original));

        int i = 1;
        do {
            if ((tmp & 1) == 1) {
                sudo[or][oc] = pointToV(i);
                System.out.println(i);
                int[][] clone = new int[9][9];
                copy(sudo, clone);
                if ((ruleSolution(clone) == 0)) {
                    if (isValidSudoku(clone)) {
                        copy(clone, sudo);
                        return true;
                    } else {
                        continue;
                    }
                }
                if (assumeSolution(clone)) {
                    copy(clone, sudo);
                    return true;
                }
            }
            tmp = tmp >> 1;
            i++;
        } while (i < 10);

        sudo[or][oc] = original;
        return false;
    }

    public static int ruleSolution(int[][] sudo) {
        int fixNum;
        do {
            candidateRow(sudo);
            candidateCol(sudo);
            candidateBlock(sudo);
            fixNum = fix(sudo);
        } while (fixNum > 0);
        return leftNum(sudo);
    }

    //候选值推算-按行
    private static void candidateRow(int[][] sudo) {
        for (int r = 0; r < 9; r++) {
            int tmp = 0;
            int value;
            for (int c = 0; c < 9; c++) {
                value = sudo[r][c];
                if ((value & CANDIDATE) == CANDIDATE) {
                    continue;
                }
                tmp = tmp | value;
            }

            if (tmp == ALL) {
                continue;
            }
            tmp = (tmp ^ ALL) | CANDIDATE;
            for (int c = 0; c < 9; c++) {
                value = sudo[r][c];
                if ((value & CANDIDATE) == CANDIDATE) {
                    sudo[r][c] = value & tmp;
                }
            }
        }
    }

    //候选值推算-按列
    private static void candidateCol(int[][] sudo) {
        for (int c = 0; c < 9; c++) {
            int tmp = 0;
            int value;
            for (int r = 0; r < 9; r++) {
                value = sudo[r][c];
                if ((value & CANDIDATE) == CANDIDATE) {
                    continue;
                }
                tmp = tmp | value;
            }

            if (tmp == ALL) {
                continue;
            }
            tmp = (tmp ^ ALL) | CANDIDATE;
            for (int r = 0; r < 9; r++) {
                value = sudo[r][c];
                if ((value & CANDIDATE) == CANDIDATE) {
                    sudo[r][c] = value & tmp;
                }
            }
        }
    }

    //候选值推算-按块
    private static void candidateBlock(int[][] sudo) {
        for (int b = 0; b < 9; b++) {
            int tmp = 0;
            int value;
            for (int i = 0; i < 9; i++) {
                value = getBlockArr(sudo, b, i);
                if ((value & CANDIDATE) == CANDIDATE) {
                    continue;
                }
                tmp = tmp | value;
            }

            if (tmp == ALL) {
                continue;
            }
            tmp = (tmp ^ ALL) | CANDIDATE;
            for (int i = 0; i < 9; i++) {
                value = getBlockArr(sudo, b, i);
                if ((value & CANDIDATE) == CANDIDATE) {
                    setBlockArr(sudo, b, i, value & tmp);
                }
            }
        }
    }

    //候选值重置
    private static void candidateReset(int[][] sudo) {
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if ((sudo[r][c] & CANDIDATE) == CANDIDATE) {
                    sudo[r][c] = CANDIDATE | ALL;
                }
            }
        }
    }

    //设置为固定唯一值(单候选值)
    private static int fix(int[][] sudo) {
        boolean[] exists = new boolean[10];
        int count = 0;
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                int v = sudo[r][c];
                if (Integer.bitCount(v) == 2 && ((v & CANDIDATE) == CANDIDATE)) {
                    int value = v & CANDIDATE_CANCEL;
                    if (exists[tran(value)]) {
                        continue;
                    }
                    sudo[r][c] = v & CANDIDATE_CANCEL;
                    exists[tran(value)] = true;
                    count++;
                }
            }
        }
        return count;
    }

    //统计需要推算的值个数
    private static int leftNum(int[][] sudo) {
        int count = 0;
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if ((sudo[r][c] & CANDIDATE) == CANDIDATE) {
                    count++;
                }
            }
        }
        return count;
    }

    private static int tran(char c) {
        switch (c) {
            case '1':
                return V1;
            case '2':
                return V2;
            case '3':
                return V3;
            case '4':
                return V4;
            case '5':
                return V5;
            case '6':
                return V6;
            case '7':
                return V7;
            case '8':
                return V8;
            case '9':
                return V9;
            default:
                return CANDIDATE | ALL;
        }
    }

    private static int pointToV(int point) {
        switch (point) {
            case 1:
                return V1;
            case 2:
                return V2;
            case 3:
                return V3;
            case 4:
                return V4;
            case 5:
                return V5;
            case 6:
                return V6;
            case 7:
                return V7;
            case 8:
                return V8;
            case 9:
                return V9;
            default:
                return 0;
        }
    }

    private static int tran(int v) {
        switch (v) {
            case V1:
                return 1;
            case V2:
                return 2;
            case V3:
                return 3;
            case V4:
                return 4;
            case V5:
                return 5;
            case V6:
                return 6;
            case V7:
                return 7;
            case V8:
                return 8;
            case V9:
                return 9;
            default:
                return 0;
        }
    }

    private static void show(int[][] sudo) {
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                int v = sudo[r][c];
                System.out.print(Integer.toBinaryString(v | 0b10000000000).substring(1, 11));
                System.out.print(" | ");
            }
            System.out.println();
        }
        System.out.println();
    }

    private static void copy(int[][] source, int[][] target) {
        int[][] clone = new int[9][9];
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                target[r][c] = source[r][c];
            }
        }
    }

    private static int getBlockArr(int[][] sudo, int block, int index) {
        int r = (block / 3) * 3 + (index / 3);
        int c = (block % 3) * 3 + (index % 3);
        return sudo[r][c];
    }

    private static void setBlockArr(int[][] sudo, int block, int index, int value) {
        int r = (block / 3) * 3 + (index / 3);
        int c = (block % 3) * 3 + (index % 3);
        sudo[r][c] = value;
    }

    public static boolean isValidSudoku(int[][] sudo) {
        //[数值1-9][行/列/块][位置]
        boolean[][][] store = new boolean[9][3][9];
        int num, blockIndex;

        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                num = tran(sudo[row][col]) - 1;
                blockIndex = getBlockIndex(row, col);
                if (store[num][0][row] || store[num][1][col] || store[num][2][blockIndex]) {
                    return false;
                }

                store[num][0][row] = true;
                store[num][1][col] = true;
                store[num][2][blockIndex] = true;
            }
        }
        return true;
    }

    public static int getBlockIndex(int row, int column) {
        int r = row / 3;
        int c = column / 3;
        return r * 3 + c;
    }

    public static void main(String[] args) {
        char[][] board_Base = new char[][]{
                {'.', '.', '.', '.', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '.', '.'}};
        char[][] board = new char[][]{
                {'.', '.', '9', '7', '4', '8', '.', '.', '.'},
                {'7', '.', '.', '.', '.', '.', '.', '.', '.'},
                {'.', '2', '.', '1', '.', '9', '.', '.', '.'},
                {'.', '.', '7', '.', '.', '.', '2', '4', '.'},
                {'.', '6', '4', '.', '1', '.', '5', '9', '.'},
                {'.', '9', '8', '.', '.', '.', '3', '.', '.'},
                {'.', '.', '.', '8', '.', '3', '.', '2', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '.', '6'},
                {'.', '.', '.', '2', '7', '5', '9', '.', '.'}};
        char[][] board_1 = new char[][]{
                {'.', '6', '1', '.', '3', '.', '.', '2', '.'},
                {'.', '5', '.', '.', '.', '8', '1', '.', '7'},
                {'.', '.', '.', '.', '.', '7', '.', '3', '4'},
                {'.', '.', '9', '.', '.', '6', '3', '7', '8'},
                {'.', '.', '3', '2', '7', '9', '5', '.', '.'},
                {'5', '7', '.', '3', '.', '.', '9', '.', '2'},
                {'1', '9', '.', '7', '6', '.', '.', '.', '.'},
                {'8', '.', '2', '4', '.', '.', '7', '6', '.'},
                {'6', '4', '.', '.', '1', '.', '2', '5', '.'}};
        char[][] board_2 = new char[][]{
                {'.', '.', '1', '3', '.', '9', '7', '.', '.'},
                {'7', '.', '.', '.', '.', '.', '.', '.', '6'},
                {'5', '6', '.', '.', '.', '.', '.', '1', '8'},
                {'.', '4', '.', '6', '9', '3', '.', '7', '.'},
                {'.', '.', '.', '.', '5', '.', '.', '.', '.'},
                {'.', '7', '.', '4', '8', '2', '.', '5', '.'},
                {'6', '3', '.', '.', '.', '.', '.', '8', '1'},
                {'2', '.', '.', '.', '.', '.', '.', '.', '9'},
                {'.', '.', '.', '9', '.', '1', '3', '.', '.'}};

        solveSudoku(board_2);
    }
}
